package 数组;

/**
 * 今天，书店老板有一家店打算试营业 customers.length 分钟。每分钟都有一些顾客（customers[i]）会进入书店，所有这些顾客都会在那一分钟结束后离开。
 * 在某些时候，书店老板会生气。如果书店老板在第 i 分钟生气，那么 grumpy[i] = 1，否则 grumpy[i] = 0。
 * 当书店老板生气时，那一分钟的顾客就会不满意，不生气则他们是满意的
 * 书店老板知道一个秘密技巧，能抑制自己的情绪，可以让自己连续 X 分钟不生气，但却只能使用一次
 * 请你返回这一天营业下来，最多有多少客户能够感到满意
 * 示例：
 * 输入：customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
 * 输出：16
 * 解释：
 * 书店老板在最后 3 分钟保持冷静。
 * 感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.
 * User: zhaixiaolong Date:2024/2/2 9:47 ProjectName: algorithm Version:
 */
public class 爱生气的书店老板 {


    public static void main(String[] args) {
        int[] customers = {1, 0, 1, 2, 1, 1, 7, 5};
        int[] grumpy = {0, 1, 0, 1, 0, 1, 0, 1};
        int x = 3;
        System.out.println(maxCustomers(customers, grumpy, x));
    }

    /**
     * 将整个数组分为3段，满意顾客数= left + window + right
     * window固定长度X
     * 移动window，计算Max(left+window+right)
     *
     * @param customers
     * @param grumpy
     * @param x
     * @return
     */
    public static int maxCustomers2(int[] customers, int[] grumpy, int x) {
        int leftSum = 0, rightSum = 0, windowSum = 0;
        int maxCustomer = 0;
        // 初始化windowSum
        for (int i = 0; i < x; i++) {
            windowSum += customers[i];
        }
        // 初始化rightSum
        for (int i = x; i < customers.length; i++) {
            if (grumpy[i] == 0) {
                // 没生气=顾客满意
                rightSum += customers[i];
            }
        }
        int leftIndex = 0, rightIndex = x;
        maxCustomer = leftIndex + windowSum + rightSum;
        while (rightIndex < customers.length) {
            if (grumpy[leftIndex] == 0) {
                leftSum += customers[leftIndex];
            }
            if (grumpy[rightIndex] == 0) {
                rightSum += customers[rightIndex];
            }
            windowSum = windowSum - customers[leftIndex] + customers[rightIndex];
            maxCustomer = Math.max(maxCustomer, leftSum + windowSum + rightSum);
            leftIndex++;
            rightIndex++;
        }
        return maxCustomer;
    }


    /**
     * 固定滑动窗口：x分钟不生气
     * 将整体分为三段：滑动窗口、窗口左，窗口右
     *
     * @param customers
     * @param grumpy
     * @param x
     * @return
     */
    public static int maxCustomers(int[] customers, int[] grumpy, int x) {
        int leftSum = 0, rightSum = 0;
        // x分钟不生气
        int windowsSum = 0;
        // 初始化窗口
        for (int i = 0; i < x; i++) {
            windowsSum += customers[i];
        }
        // 右边和
        for (int i = x; i < customers.length; i++) {
            if (grumpy[i] == 0) {
                // 没生气
                rightSum += customers[i];
            }
        }
        // 初始窗口右移动1位
        int leftIndex = 0, rightIndex = x;
        // 最大值
        int maxSum = leftSum + windowsSum + rightSum;
        while (rightIndex < customers.length) {
            // 左边sum
            if (grumpy[leftIndex] == 0) {
                leftSum += customers[leftIndex];
            }
            // 右边sum
            if (grumpy[rightIndex] == 0) {
                rightSum -= customers[rightIndex];
            }
            // 窗口sum
            windowsSum = windowsSum - customers[leftIndex] + customers[rightIndex];
            maxSum = Math.max(maxSum, leftSum + windowsSum + rightSum);
            leftIndex++;
            rightIndex++;
        }
        return maxSum;


    }

}
